package com.urbanski.util.collections;

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * A set that tracks whether an element was (attempted to be) added multiple times. If an element is
 * added while the set already contains it, then it is removed from the set and may not be added
 * again.
 * 
 * This set is useful for finding unique instances in a collection that contains both unique and
 * non-unique elements.
 * 
 * For example, assume the collection C has the following elements:
 * 
 * [A, B, B, C, D, D, D, E]
 * 
 * After adding each element to the set (via the Collection constructor or the addAll method), the
 * set will contain the following elements:
 * 
 * [A, C, E]
 * 
 * If, later, E is "added" to the set, then the set will no longer contain E.
 * 
 * @author murbanski004
 * 
 * @param <E>
 */
public class RemoveDuplicatesSet<E> implements Set<E>
{
	private Set<E> duplicateSet = new HashSet<E>();
	private Set<E> actualSet = new HashSet<E>();

	/**
	 * Constructs a new, empty set
	 */
	public RemoveDuplicatesSet()
	{

	}

	/**
	 * Constructs a new set and adds all elements in the specified collection. See the class, add,
	 * and addAll documentation for details on what it means to "add" an element to this set.
	 * 
	 * @param c
	 */
	public RemoveDuplicatesSet(Collection<? extends E> c)
	{
		addAll(c);
	}

	@Override
	/**
	 * Adds the specified element to this set. If this set already contains the element, then the
	 * element will be removed, and subsequent attempts to add this element will not modify the set.
	 * 
	 * For a given element e, the first attempt to add e to this set will result in a return value
	 * of true; all subsequent calls will return false (unless remove is called - see that method's
	 * documentation)
	 * 
	 * @return true if the element was added (it was not already contained), or false if the element
	 *         was already contained (or previously contained and subsequently added).
	 */
	public boolean add(E e)
	{
		if (!duplicateSet.contains(e) && !actualSet.contains(e))
		{
			actualSet.add(e);
			return true;
		}
		else
		{
			duplicateSet.add(e);
			actualSet.remove(e);
			return false;
		}
	}

	@Override
	/**
	 * Adds all elements of the specified collection to this set.  The functionality
	 * is equivalent to calling the add method for each element in the set in iteration order.
	 * 
	 * @return true if at least one of the elements in the collection was not previously contained in the set
	 * (that is, if the add method returns true at least once)
	 */
	public boolean addAll(Collection<? extends E> c)
	{
		boolean ret = false;

		for (E e : c)
		{
			ret |= add(e);
		}

		return ret;
	}

	@Override
	/**
	 * Removes all elements from this set and resets their "uniqueness".  After calling the clear method,
	 * the next call to add will always succeed, regardless of whether the element being added was
	 * ever contained in this set.
	 */
	public void clear()
	{
		actualSet.clear();
		duplicateSet.clear();
	}

	@Override
	/**
	 * Returns whether or not the specified object has been added to this set exactly once
	 * 
	 * @return true if the specified object has been added to this set (via any of the add operations -
	 * the constructor, add, or addAll) exactly once, or false if the element has never been added to this
	 * set or has been added multiple times.
	 */
	public boolean contains(Object o)
	{
		return actualSet.contains(o);
	}

	@Override
	/**
	 * Returns whether or not this set contains all elements in the specified set, using the definition
	 * of "contains" defined by the contains method.
	 */
	public boolean containsAll(Collection<?> c)
	{
		for (Object o : c)
		{
			if (!contains(o))
			{
				return false;
			}
		}
		
		return true;
	}

	@Override
	/**
	 * Returns whether or not the number of unique elements in the set is 0.  For example, assume
	 * the following elements have been added to this set:
	 * 
	 * [A, B, B]
	 * 
	 * Because A is unique, isEmpty returns false.  If A were subsequently added again, then isEmpty
	 * would return true.
	 */
	public boolean isEmpty()
	{
		return actualSet.isEmpty();
	}

	@Override
	/**
	 * Returns an iterator over the unique elements of the set (all elements that have been added exactly once).
	 */
	public Iterator<E> iterator()
	{
		return actualSet.iterator();
	}

	@Override
	/**
	 * Removes the specified object from this set and resets it.  Removing an element e will cause a subsequent
	 * attempt to add e to succeed.  The return value can be said to be the opposite of the return value of
	 * an attempt to add the specified object without calling the remove method.
	 * 
	 * For example, if element A had never been added to this set, then calling remove(A) would return false, but
	 * calling add(A) instead would return true, and vice versa.
	 * 
	 * @return true if the specified object has ever been added to this set
	 */
	public boolean remove(Object o)
	{
		return actualSet.remove(o) || duplicateSet.remove(o);
	}

	@Override
	/**
	 * Removes all elements of the specified collection, using the "remove" definition defined by the remove method.
	 * @return true if at least one element in the collection was reset (that is, if calling the remove method on
	 * that element would've returned true)
	 */
	public boolean removeAll(Collection<?> c)
	{
		return actualSet.removeAll(c) || duplicateSet.removeAll(c);
	}

	@Override
	/**
	 * This method is not supported, as it does not functionally make sense.
	 */
	public boolean retainAll(Collection<?> c)
	{
		throw new UnsupportedOperationException("This method is not supported");
	}

	@Override
	/**
	 * Returns the number of elements that have been added to this set exactly once
	 */
	public int size()
	{
		return actualSet.size();
	}

	@Override
	/**
	 * Returns an array containing the elements that have been added to this set exactly once
	 */
	public Object[] toArray()
	{
		return actualSet.toArray();
	}

	@Override
	/**
	 * Returns an array containing the elements that have been added to this set exactly once
	 */
	public <T> T[] toArray(T[] a)
	{
		return actualSet.toArray(a);
	}

}
